The preparation, storage and transmission of video data, and, in particular, video graphics data generated by a computer (for example, video graphics data for a computer game), require extensive computer resources and broadband network connections. These requirements are particularly severe when such data are transmitted in real time among a group of individuals connected over a local area network or a wide area network such as the Internet. Such transmitting occurs, for example, when video games are played over the Internet. Such playing, moreover, is becoming increasingly popular.
In order to reduce the amount of network capacity and computer resources required for the transmission of video data, various encoding schemes for data compression are employed. These data compression schemes include various versions of the MPEG (Motion Picture Experts Group) encoding standard, for example, MPEG-1, MPEG-2 and MPEG-4, and others. These data compression schemes reduce the amount of image information required for transmitting and reproducing motion picture sequences by eliminating redundant and non-essential information in the sequences.
For example, the only difference in many cases between two adjacent frames in a motion picture sequence is the slight shifting of certain blocks of pixels. Large blocks of pixels, representing, for example, regions of sky, walls and other stationary objects, often do not change at all between consecutive frames. Compression algorithms such as MPEG exploit this temporal redundancy to reduce the amount of data transmitted or stored for each frame.
For example, in the MPEG standard, three types of frames are defined, namely, intra frames (I-frames), predicted frames (P-frames) and bi-directionally interpolated frames (B-frames). As illustrated in FIG. 1, I-frames are reference frames for B-frames and P-frames and are only moderately compressed. P-frames are encoded with reference to a previous frame. The previous frame can be either an I-frame or a P-frame. B-frames are encoded with reference to both a previous frame and a future frame. The reference frames for B-frames also can be either an I-frame or a P-frame. B-frames are not used as references.
In order to encode predicted frames and interpolated frames from reference frames, the MPEG scheme uses various motion estimation algorithms. These motion estimation algorithms include full search algorithms, hierarchical searching algorithms and telescopic algorithms. As illustrated in FIG. 2, under the MPEG standard, each frame typically is divided into blocks of 16 by 16 pixels called a macro block. A macro block of a current frame is encoded using a reference frame by estimating the distance that the macro block moved in the current frame from the block's position in the reference frame. The motion estimation algorithm performs this estimating by comparing each macro block of the current frame to macro blocks within a search area of the reference frame to find the best matching block in the reference frame. For example, for macro block 201 of current frame 207, a comparison is made within search area 203 of reference frame 209 between macro block 201 of the current frame and each macro block 205 of the reference frame to find the best matching block in the reference frame. The position of this best matching macro block within the reference frame then is used to calculate a motion vector for macro block 201 of the current frame. Rather than transmit for current frame 207 all of the video data corresponding to macro block 201, only the motion vector is transmitted for this block. In this way, the video data for the current block are compressed.
Executing motion estimation algorithms, however, also requires substantial computer resources. Since each macro block of a current frame must be compared to numerous macro blocks of one or more reference frames, an extensive number of computations are required. For example, the three-step-search algorithm (TSS) (a hierarchical algorithm) evaluates matches at a center location and eight surrounding locations of a search area. The location that produces the smallest difference then becomes the center of the next search area to reduce the search area by one-half. This sequence is repeated three times.
A need exists, therefore, for a more efficient and effective method for compressing video graphics data, particularly in view of the increasing demand for systems capable of playing video games in real time over the Internet and other networks.